package LC;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @ClassName LC415
 * @Description: TODO
 * @Author hl
 * @Date 2020/10/12
 * @Version V1.0
 **/
public class LC415 {
    public static void main(String[] args) {
        System.out.println(frequencySort("tree"));
    }public static String frequencySort(String s) {
        HashMap<Character,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        List<Character>[] frequency=new ArrayList[s.length()+1];
        for(Character key:map.keySet()){
            int value=map.get(key);//次数
            if(frequency[value]==null){
                frequency[value]=new ArrayList<>();
            }
            frequency[value].add(key);

        }
        String res="";
        for(int j=frequency.length-1;j>=0;j--){
            if(frequency[j]!=null){
                for(int c=0;c<frequency[j].size();c++){
                    for(int z=0;z<j;z++){
                        res+=frequency[j].get(c);
                    }
                }
            }
        }
        return  res;
    }

}
